package 滑动窗口最大值;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;



/**
 * @author zhengTao
 * @version 1.0
 * @description: 滑动窗口最大值
 * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 * @date 2022/10/23 16:32
 */
public class Demo239 {
   static List<Integer> list=new LinkedList<>();
    public static void main(String[] args) {
        //[1,3,1,2,0,5]

        //3
        int[] nums= {1,3,1,2,0,5};
        int k= 3;
        int[] ints = maxSlidingWindow(nums, k);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length<k){
            return new int[]{};
        }
        //记录最大值的数组
        int[] num=new int[nums.length-k+1];

        int index=0;
        for (int i = 0; i < k; i++) {
            addLast(nums[i],list);
        }
        num[index++]=list.get(0);
        for (int i = k; i < nums.length; i++) {
            deleteFirst(nums[i-k],list);
            addLast(nums[i],list);
            num[index++]=list.get(0);
        }
        return num;
    }

    private static void deleteFirst(int i, List<Integer> list) {
        if(i==list.get(0)){
            list.remove(0);
        }
    }

    private static void addLast(int i, List<Integer> list) {
        if(list.isEmpty()||list.get(list.size()-1)>i){
            list.add(i);
        }else {
            while (!list.isEmpty()&&list.get(list.size()-1)<i){
                list.remove(list.size()-1);
            }
            list.add(i);
        }
    }


}
